package com.yanceysong.codetop.s41_s50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class S44_Mid_22_括号生成 {
    /**
     * LeetCode 链接： <a href="https://leetcode.cn/problems/generate-parentheses/">...</a>
     * 题目描述：
     * 给定 n 对括号，请编写一个函数，用于生成所有可能且有效的括号字符串。
     * <p>
     * 示例：
     * 输入：n = 3
     * 输出：[("((()))","(()())","(())()","()(())","()()()")]
     * <p>
     * 提示：
     * 1 <= n <= 8
     * <p>
     * 使用回溯（backtracking）构造所有合法的括号序列。
     * - 每一步可以选择添加左括号 '('（前提：已使用的左括号数量 < 对数 n）
     * - 或者添加右括号 ')'（前提：已使用的右括号数量 < 已使用的左括号数量）
     * 只有当构建的字符串长度达到 2*n 时，将其加入结果集。
     * <p>
     * 关键洞察（ASCII 图示）：
     * 以 n=3 为例，回溯树（部分）：
     * <p>
     * .""
     * . ├─ "("
     * . │   ├─ "(("
     * . │   │   ├─ "(((" -> "((()))"
     * . │   │   └─ "(()" -> ...
     * . │   └─ "()" -> ...
     * . └─  无
     * <p>
     * 复杂度分析：
     * 时间复杂度：O(4^n / sqrt(n))，生成所有合法括号的数量等同于第 n 个卡特兰数。
     * 空间复杂度：O(4^n / sqrt(n))，用于存储结果集和递归栈。
     */
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        // 使用 StringBuilder 做可变字符拼接，避免频繁创建字符串对象
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    /**
     * 回溯函数
     *
     * @param result     最终结果列表
     * @param current    当前构建的字符串（使用 StringBuilder 提高性能）
     * @param openCount  当前已放置的左括号数量 '('
     * @param closeCount 当前已放置的右括号数量 ')'
     * @param maxPairs   总的括号对数 n
     */
    public void backtrack(List<String> result, StringBuilder current, int openCount, int closeCount, int maxPairs) {
        // 当已构建长度达到 2 * n 时，说明构建完成，将当前字符串加入结果
        if (current.length() == maxPairs * 2) {
            result.add(current.toString());
            return;
        }

        // 尝试放置一个左括号（如果还有剩余的左括号）
        if (openCount < maxPairs) {
            // 选择
            current.append('(');
            backtrack(result, current, openCount + 1, closeCount, maxPairs);
            // 撤销选择，回溯到上一步状态
            current.deleteCharAt(current.length() - 1);
        }

        // 尝试放置右括号的条件：已放置右括号少于已放置左括号，保证前缀仍然合法
        if (closeCount < openCount) {
            current.append(')');
            backtrack(result, current, openCount, closeCount + 1, maxPairs);
            // 撤销选择
            current.deleteCharAt(current.length() - 1);
        }
    }

    /**
     * 主方法：组织并运行测试用例
     */
    public static void main(String[] args) {
        S44_Mid_22_括号生成 solution = new S44_Mid_22_括号生成();

        System.out.println("=== 生成括号 测试开始 ===");

        // 测试1：n=0（边界，部分实现返回 [""]）
        System.out.println("\n--- 测试1: n=0 （边界）---");
        testGenerate(solution, 0, Arrays.asList(""));

        // 测试2：n=1
        System.out.println("\n--- 测试2: n=1 ---");
        testGenerate(solution, 1, Arrays.asList("()"));

        // 测试3：n=2
        System.out.println("\n--- 测试3: n=2 ---");
        testGenerate(solution, 2, Arrays.asList("()()", "(())"));

        // 测试4：n=3（题目示例）
        System.out.println("\n--- 测试4: n=3 ---");
        testGenerate(solution, 3, Arrays.asList("((()))", "(()())", "(())()", "()(())", "()()()"));

        // 测试5：n=4（检查结果数量）
        System.out.println("\n--- 测试5: n=4 ---");
        List<String> resN4 = solution.generateParenthesis(4);
        System.out.println("n=4 生成数量: " + resN4.size() + ", 结果 (部分): " + (resN4.size() <= 20 ? resN4 : resN4.subList(0, 20)));
        assert resN4.size() == 14 : "n=4 应该生成 14 个合法括号组合";
        System.out.println("✓ n=4 测试通过，生成 14 个组合");

        // 测试6：n=5（检查结果数量，卡特兰数 C5 = 42）
        System.out.println("\n--- 测试6: n=5 ---");
        List<String> resN5 = solution.generateParenthesis(5);
        System.out.println("n=5 生成数量: " + resN5.size());
        assert resN5.size() == 42 : "n=5 应该生成 42 个合法括号组合";
        System.out.println("✓ n=5 测试通过，生成 42 个组合");

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * 辅助测试方法：验证生成结果是否包含期望集合（不要求顺序）
     */
    private static void testGenerate(S44_Mid_22_括号生成 solution, int n, List<String> expectedList) {
        List<String> actual = solution.generateParenthesis(n);
        System.out.println("输入 n = " + n + "，生成 " + actual.size() + " 个组合: " + actual);

        // 将两个列表转为集合比较，不要求顺序
        Set<String> actualSet = new HashSet<>(actual);
        Set<String> expectedSet = new HashSet<>(expectedList);

        // 验证期望集合是实际集合的子集（实际生成可能包含更多组合时，只检查期望）
        if (!actualSet.containsAll(expectedSet)) {
            System.out.println("生成结果缺少期望的组合，期望: " + expectedSet + " 实际: " + actualSet);
            throw new AssertionError("生成结果不包含所有期望组合");
        }

        System.out.println("✓ 测试通过 (包含期望的组合)");
    }
}
